import math
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
# l1=ListNode(1)
# l1.next=ListNode(0)
# l1.next.next=ListNode(0)
# l1.next.next.next=ListNode(0)
# l1.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next.next.next.next.next=ListNode(0)
# l1.next.next.next.next.next.next.next.next.next.next.next=ListNode(0)
# l2=ListNode(9)
# l2.next=ListNode(9)
# l2.next.next=ListNode(9)
# l2.next.next.next=ListNode(9)
def creat_List(l):
    l_p=ListNode()
    l_p_1=l_p
    i=0
    while i<len(l):
        l_p_1.val=l[i]
        if i+1<len(l):
            l_p_1.next=ListNode()
            l_p_1=l_p_1.next
        i+=1
    return l_p
l_1=[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
l_2=[5,6,4]
l_1_p=creat_List(l_1)
l_2_p=creat_List(l_2)
# l_p=creat_List(l
# l_p_r=l_p
# while l_p_r!=None:
#     print(l_p_r.val)
#     l_p_r=l_p_r.next
def addTwoNumbers(l1,l2):
    #创建两个操作指针
    p_1,p_2=l1,l2
    #创建新的头
    l=ListNode(0,None)
    l_1=l
    carry=False
    l_2=l
    i=0
    while p_1 and p_2:
        #指针p_1和p_2都不指向空
        if carry:
            l_1.val+=p_1.val+p_2.val+1
            carry=False
        else:
            l_1.val+=p_1.val+p_2.val
        if l_1.val>=10:
            carry=True
            l_1.val-=10
        p_1=p_1.next
        p_2=p_2.next
        l_1.next=ListNode(0,None)
        l_1=l_1.next
        if i>=1:
            l_2=l_2.next
        i+=1
    while p_1:
        if carry:
            l_1.val+=p_1.val+1
            carry=False
        else:
            l_1.val+=p_1.val
        if l_1.val>=10:
            carry=True
            l_1.val-=10
        p_1=p_1.next
        l_1.next=ListNode(0,None)
        l_1=l_1.next
        if i>=1:
            l_2=l_2.next
        i+=1
    while p_2:
        if carry:
            l_1.val+=p_2.val+1
            carry=False
        else:
            l_1.val+=p_2.val
        if l_1.val>=10:
            carry=True
            l_1.val-=10
        p_2=p_2.next
        l_1.next=ListNode(0,None)
        l_1=l_1.next
        if i>=1:
            l_2=l_2.next
        i+=1
    if carry:
        l_1.val=1
    else:
        l_2.next=None
    l_2=l
    while l_2:
        print(l_2.val,"-> ")
        l_2=l_2.next

addTwoNumbers(l_1_p,l_2_p)